#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
ll jc[3000005], inv[3000005];
ll qp(ll x, ll y){
	ll ans=1;
	for(; y; y/=2,x=x*x%mod){
		if(y&1) ans=ans*x%mod;
	}
	return ans;
}
ll baoC(ll x, ll y){
	if(x<0||y<0||x<y) return 0;
	ll res=1;
	for(ll i=x; i>x-y; --i) res=res*i%mod;
	res=res*inv[y]%mod;
	return res;
}
ll Lucas(ll x, ll y);
ll C(ll x, ll y) {
	if(x<0||y<0||x<y) return 0;
	if(x>=mod) return Lucas(x, y);
	return jc[x]*inv[x-y]%mod*inv[y]%mod;
}
ll Lucas(ll x, ll y){
	ll ans=1;
	while(x&&y){
		ans=ans*C(x%mod, y%mod)%mod;
		x/=mod, y/=mod;
	}
	return ans;
}
void add(ll &x, ll y){
	x=(x+y)%mod;
}
void init() {
	int N=min((int)3e6, mod-1);
	jc[0]=1;
	for(int i=1; i<=N; ++i){
		jc[i]=jc[i-1]*i%mod;
	}
	inv[N]=qp(jc[N], mod-2);
	for(int i=N-1; i>=0; --i){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
}
const int N=2005, M=4e6+5;
ll f[N], g[N];
int px[M], py[M];
vector<int> e[N];
int d[N], fr[N];
int n, m;
void bfs(int s){
	for(int i=1; i<=n; ++i){
		d[i]=0;
	}
	d[s]=1;
	fr[s]=0;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(auto y:e[x]){
			if(!d[y]){
				d[y]=d[x]+1;
				fr[y]=x;
				q.push(y);
			}
		}
	}
}
int ans; ll ct;
int fa[N], dep[N];
void dfs(int x, int ff){
	fa[x]=ff;
	dep[x]=dep[ff]+1;
	for(auto y:e[x]){
		if(y==ff) continue;
		if(!dep[y]) dfs(y, x);
		else if(dep[x]-dep[y]+1==ans){
			ct++;
		}
	}
}
int main(){
	init();
	freopen("oi.in", "r", stdin);
	freopen("oi.out", "w", stdout);
	f[0]=f[1]=f[2]=1;
	g[0]=g[1]=g[2]=1;
	for(int i=3; i<N; ++i){
		for(int j=1; j<i; ++j){
			add(g[i], f[j]*f[i-j]);
		}
		for(int j=2; j<=i; ++j){
			add(f[i], g[j]*f[i-j+1]);
		}
	}
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int c, T;
	cin >> c >> T;
	while(T--){
		cin >> n >> m;
		for(int i=1, x, y; i<=m; ++i){
			cin >> x >> y;
			px[i]=x, py[i]=y;
		}
		if(c>=3&&c<=4){
			printf("%d %lld\n", -2*n+2, f[n]);
			continue;
		}
		for(int i=1; i<=n; ++i){
			vector<int>().swap(e[i]);
		}
		for(int i=1; i<=m; ++i){
			int x=px[i], y=py[i];
			e[x].push_back(y);
			e[y].push_back(x);
		}
		ans=1e9, ct=0;
		for(int i=1; i<=n; ++i){
			bfs(i);
			for(int j=1; j<=m; ++j){
				int x=px[j], y=py[j];
				if(d[x]<d[y]) swap(x, y);
				if(!d[x]||!d[y]||fr[x]==y) continue;
				int res=d[x]+d[y]-1;
				ans=min(ans, res);
			}
		}
		if(c>=5&&c<=6){
			for(int i=1; i<=n; ++i){
				dep[i]=0;
			}
			for(int i=1; i<=n; ++i){
				if(!dep[i]) dfs(i, 0);
			}
			printf("%d %lld\n", -m-ans+2, (f[ans]*ct)%mod);
			continue;
		}
		printf("%d %lld\n", -m-ans+2, 0ll);
//		if(c>=7&&c<=9){
//			for(int i=1; i<=n; ++i){
//				dep[i]=0;
//			}
//			vector<int> vc;
//			for(int i=1; i<=n; ++i){
//				if(e[i].size()>2) vc.push_back(i);
//			}
//			if(!vc.size()){
//				printf("%d %lld\n", -2*n+2, f[n]);
//			}else{
//				bfs(vc[0]);
//				int t=d[vc[1]];
//				dep[vc[0]]=1, dep[vc[1]]=t;
//				dfs(vc[1], fr[vc[1]]);
//				printf("%d %lld\n", -m-ans+2, (f[ans]*ct)%mod);
//			}
//			continue;
//		}
	}
	return 0;
}


